package com.kwt.learn.algorithm;

import java.util.Arrays;
import java.util.HashMap;

/**
 * 设计LRU缓存结构
 * 设计LRU缓存结构，该结构在构造时确定大小，假设大小为K，并有如下两个功能
 * set(key, value)：将记录(key, value)插入该结构
 * get(key)：返回key对应的value值
 * [要求]
 * set和get方法的时间复杂度为O(1)
 * 某个key的set或get操作一旦发生，认为这个key的记录成了最常使用的。
 * 当缓存的大小超过K时，移除最不经常使用的记录，即set或get最久远的。
 * 若opt=1，接下来两个整数x, y，表示set(x, y)
 * 若opt=2，接下来一个整数x，表示get(x)，若x未出现过或已被移除，则返回-1
 * 对于每个操作2，输出一个答案
 * <p>
 * [[1,1,1],[1,2,2],[1,3,2],[2,1],[1,4,4],[2,2]],3
 * <p>
 * [1,-1]
 */
public class Solution07 {
    HashMap<Integer, Node> keyIndex = new HashMap<Integer, Node>();// key Node
    //定义链表头部节点
    Node head = new Node();
    //定义链表尾部节点
    Node tail = new Node();

    static class Node {
        //双向链表实现
        public Node pre;//表示上一个节点
        public Node next;//表示下一个节点
        public int key;// key
        public int value; //当前节点存储的值

        Node(int key, int value) {
            this.key = key;
            this.value = value;
        }

        Node() {
        }
    }

    /**
     * 存取的所有的过程方法
     *
     * @param operators
     * @param k
     * @return
     */
    public int[] LRU(int[][] operators, int k) {
        int len = (int) Arrays.stream(operators).filter(x -> x[0] == 2).count();
        int[] ret = new int[len];
        int count = 0;
        /**
         * 设计核心 ： 大小固定（超出固定长度时，移除最不常使用的）、最长使用（set/get方法）
         * 数组第一个元素表示动作，1表示set 2表示get
         * set方法
         * get方法
         * removeToHead 将某个节点移动到链表头部
         */
        // 使用双向链表和 HashMap 完成一个LRU缓存，map用于O(1)查找索引，双向链表用于存储数据
        for (int[] operator : operators) {
            if (operator[0] == 1) {
                //set
                set(operator[1], operator[2], k);
            }
            if (operator[0] == 2) {
                //get
                ret[count] = get(operator[1]);
                count++;
            }
        }

        return ret;
    }

    /**
     * @param key
     * @param value
     * @return
     */
    public boolean set(int key, int value, int k) {
        //如果map中还没有值，
        if (keyIndex.size() <= 0) {
            head = new Node(key, value);
            tail = head;
        }
        // 判断长度
        if (keyIndex.size() > k) {
            //需要將尾部节点移除，移除后再往头部放入数据
            tail.pre.next = null;
            tail = tail.pre;
        }
        //新插入的数据都往链表的头部放
        Node node = new Node(key, value);
        head.pre = node;
        node.next = head;
        head = node;
        //將key和Node存储到map中，便于查询
        keyIndex.put(key, node);
        return true;
    }

    /**
     * get方法 从hashmap中获取
     *
     * @param key
     * @return
     */
    public int get(int key) {
        //如果能获取到，说明有对应的val
        //如果获取不到返回-1；
        Node val = null;
        if ((val = keyIndex.get(key)) != null) {
            //将该节点移动到头部
            moveToHead(val);
            //判断并返回value数据
            return val.key == key ? val.value : -1;
        }
        return -1;
    }

    /**
     * 将该节点移动到链表的头部位置
     * 永远保持最活跃的节点在头部
     * <p>
     * 移动某个节点的时候，判断是否移动的最后一个节点，如果是最后一个节点，维护尾结点对象
     *
     * @param node
     */
    public void moveToHead(Node node) {
        if (node.pre == null) {
            return;
        }
        //判断node节点是不是尾结点，如果是
        if (node.next == null) {
            tail = node.pre;
        }
    }
}
